#include "util.h"
#include "common_sort.h"

void HeapSort::sort(std::vector<int>& vec) {
	int sz = vec.size();
	
	int lastIndex = sz - 1;
	// heapify
	for (int i = (lastIndex - 1) / 2; i >= 0; --i) {
		heapify(vec, sz, i);
	}

	// sort
	for (int i = sz - 1; i > 0; --i) {
		util::swap(vec, 0, i);

		heapify(vec, i, 0);
	}
}

// 从rootIndex开始往下堆化
void HeapSort::heapify(std::vector<int>& vec, int sz, int rootIndex) {
	if (rootIndex >= sz) return;

	int largest = rootIndex;
	int left = 2 * rootIndex + 1;
	int right = 2 * rootIndex + 2;

	if (left < sz && vec[left] > vec[largest]) {
		largest = left;
	}

	if (right < sz && vec[right] > vec[largest]) {
		largest = right;
	}

	if (largest != rootIndex) {
		util::swap(vec, rootIndex, largest);
		heapify(vec, sz, largest);
	}
}


